package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author feizns
 * @since 2020/3/10
 */
public class WidthOfBinaryTree {

    public static void main(String[] args) {
        final int i = widthOfBinaryTree(create());
        System.out.println(i);
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(3);
        ret.right = new TreeNode(2);
        ret.left.left = new TreeNode(5);
        ret.left.right = new TreeNode(3);
        ret.right.right = new TreeNode(9);
        return ret;
    }

    public static int widthOfBinaryTree(TreeNode root) {
        int max = root != null ? 1 : 0;
        Queue<NoP> queue = new LinkedList<>();
        if ( root != null )
            queue.add(new NoP(root, 0));
        while ( !queue.isEmpty() ) {
            int size = queue.size();
            int v = queue.peek().val;
            for (int i = 0; i < size; i++) {
                NoP node = queue.remove();
                max = Math.max((node.val - v) + 1, max);
                if ( node.node.left != null)
                    queue.add(new NoP(node.node.left, node.val * 2 + 1));
                if ( node.node.right != null )
                    queue.add(new NoP(node.node.right, node.val * 2 + 2));
            }
        }
        return max;
    }

    static class NoP {
        TreeNode node;
        int val;
        public NoP(TreeNode node, int val) {
            this.node = node;
            this.val = val;
        }
    }

}
